#include "../Basics/BasicStruct.cpp"

// 链表简单排序
List NormalSortList(List list) {
    ListNode *head = (ListNode*) malloc(sizeof(ListNode));
    head->next = NULL;
    // 遍历整条链表的节点
    ListNode* pos = list;
    while(pos != NULL)//一遍遍地找原链表中当前最大结点
    {
        //p：遍历出最大值的指针
        ListNode* p=pos->next;
        //max: 原链表中最大的结点 preMax: 最大结点的前驱结点 pre: p的前驱结点
        ListNode *max=pos,*preMax=pos,*pre=pos;
        // 寻找最大结点
        while(p){
            if(p->data > max->data){
                // 如果发现最大值,需要更新他的前驱和他本身
                max=p;
                preMax=pre;
            }
            pre=p;
            p=p->next;
        }
        // 让这个结点离开原链表 即连接最大值的前驱和他的后继.
        if(max==pos)//如果找到的结点是第一个结点
            pos=pos->next;//让头指针向后移一位
        else
            preMax->next=max->next;
        // 把最大值头插法插入新链表
        max->next= head->next;
        head->next = max;
    }
    return head->next;
}



int main() {
    List list= CreateList();
    List newList = NormalSortList(list);
    PrintList(newList);
}